package problems

// 933
// https://leetcode-cn.com/problems/number-of-recent-calls/
type RecentCounter struct {
	queue []int
}

func RecentCounterConstructor() RecentCounter {
	return RecentCounter{queue: make([]int, 0)}
}

func (rc *RecentCounter) Ping(t int) int {
	rc.queue = append(rc.queue, t)
	var index = 0
	for i := 0; i < len(rc.queue); i++ {
		if t-rc.queue[i] <= 3000 {
			break
		}
		index++
	}
	rc.queue = rc.queue[index:]
	return len(rc.queue)
}

// 938
// https://leetcode-cn.com/problems/range-sum-of-bst/
func RangeSumBST(root *TreeNode, L int, R int) int {
	var sum int
	var order func(root *TreeNode)
	order = func(root *TreeNode) {
		if root != nil {
			if root.Val >= L && root.Val <= R {
				sum += root.Val
			}
			if root.Val >= L {
				order(root.Left)
			}
			if root.Val <= R {
				order(root.Right)
			}
		}
	}
	order(root)
	return sum
}

// 965
// https://leetcode-cn.com/problems/univalued-binary-tree/
func IsUniValTree(root *TreeNode) bool {
	if root == nil {
		return false
	}
	var isUni = true
	var order func(root *TreeNode, val int)
	order = func(root *TreeNode, val int) {
		if isUni && root != nil {
			if root.Val != val {
				isUni = false
			} else {
				order(root.Left, val)
				order(root.Right, val)
			}
		}
	}
	order(root, root.Val)
	return isUni
}

// SortedSquares
// 977
// https://leetcode-cn.com/problems/squares-of-a-sorted-array/
func SortedSquares(nums []int) []int {
	res := make([]int, len(nums))
	l, r, ls, rs := 0, len(nums)-1, 0, 0
	for i := len(nums) - 1; i >= 0; i-- {
		ls, rs = nums[l]*nums[l], nums[r]*nums[r]
		if ls < rs {
			res[i] = rs
			r--
		} else {
			res[i] = ls
			l++
		}
	}

	return res
}

// 978
// https://leetcode-cn.com/problems/longest-turbulent-subarray/
func MaxTurbulenceSize(arr []int) int {
	max, up, down := 1, 1, 1
	for i := 1; i < len(arr); i++ {
		if arr[i] > arr[i-1] {
			up, down = 1, up+1
		} else if arr[i] < arr[i-1] {
			up, down = down+1, 1
		} else {
			up, down = 1, 1
		}
		if up > max {
			max = up
		}
		if down > max {
			max = down
		}
	}
	return max
}

// 993
// https://leetcode-cn.com/problems/cousins-in-binary-tree/
func IsCousins(root *TreeNode, x int, y int) bool {
	if root == nil {
		return false
	}
	var xNode, yNode, pXNode, pYNode *TreeNode
	var lastStack, stack, curStack []*TreeNode
	stack = []*TreeNode{root}
	for len(stack) > 0 {
		for _, v := range stack {
			if v.Val == x {
				xNode = v
			} else if v.Val == y {
				yNode = v
			}
			if v.Left != nil {
				curStack = append(curStack, v.Left)
			}
			if v.Right != nil {
				curStack = append(curStack, v.Right)
			}
		}
		if xNode != nil && yNode != nil {
			for _, v := range lastStack {
				if v.Left == xNode || v.Right == xNode {
					pXNode = v
				} else if v.Left == yNode || v.Right == yNode {
					pYNode = v
				}
			}
			if pXNode != nil && pYNode != nil && pXNode != pYNode {
				return true
			}
			return false
		}
		xNode, yNode, pXNode, pYNode = nil, nil, nil, nil
		lastStack, stack, curStack = stack, curStack, []*TreeNode{}
	}
	return false
}
